package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-12 23:39
 */
public class DifferentWay {
    public static void main(String[] args) {

    }

    /**leetcode 62
     * 五部曲：1.我们初始化为一个二维数组，数组的下标代表当前走到的位置，数组的大小代表当前走到这个位置的方法数2.递推公式，考虑到
     * 走到每一个格子之前只能由这个格子的左边和格子的上边推出来，所以递推公式应该这样理解：dp[i][j]=dp[i][j-1]+dp[i-1][j]
     * 3.初始化数组：由于每个元素都是有其上面的元素和左边的元素相加而来，所以需要初始化最上面和最左边的一行和一列元素
     * v
     * @param way
     * @param rol
     * @param column
     * @return
     */
    public static int differentWay(int[][]way,int rol,int column){
        //初始化数组
        int[][]dp=new int[rol+1][column+1];
        //第一行初始化
        for(int i=0;i< dp.length;++i){
            dp[i][0]=1;
        }
        //第一列初始化
        for(int i=0;i<dp[0].length;++i){
           dp[0][i]=1;

            }
        //遍历数组
        for(int i=1;i<dp.length;++i){
            for (int j = 1; j <dp[0].length ; j++) {
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[rol][column];
        }

    }

